package com.zfl;

public class LengthOfLIS {

    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] tails = new int[n];

        int left = 0;
        int right = 0;
        int len = 0;

        for (int num : nums) {
            right = len;
            left = 0;
            //二分查找找到第一个位置num小于tails[i]
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (num > tails[mid]) {
                    left=mid+1;
                } else {
                    right=mid;
                }
            }

            tails[left]=num;
            if (left==len) {
                len++;
            }


        }
        return len;
    }
}
